package interview.lca;

import interview.common.BinaryTreeNode;

public class LCA {
	public BinaryTreeNode lca(BinaryTreeNode root, BinaryTreeNode n1, BinaryTreeNode n2, int[] count) {
		if (root == null) {
			return null;
		}

		BinaryTreeNode node = lca(root.getLeft(), n1, n2, count);
		if (n1.getData() == n2.getData() && count[0] == 1) {
			return node;
		}

		if (count[0] == 2) {
			return node;
		}

		if (root.getData() == n1.getData() || root.getData() == n2.getData()) {
			count[0]++;
			if (n1.getData() == n2.getData() && count[0] == 1) {
				return root;
			}
		}

		if (count[0] == 2) {
			return root;
		} else {
			node = lca(root.getRight(), n1, n2, count);
			if (n1.getData() == n2.getData() && count[0] == 1) {
				return node;
			}
			
			if (count[0] == 2) {
				return root;
			} else {
				return null;
			}
		}
	}
}
